Parallel resolution of triangular systems
Abstract
The resolution of triangular systems is a computational nucleus widely used in various scientific applications. This research performs the implementation and comparison of several parallel algorithms against an efficient sequential algorithm for solving triangular systems. The algorithms are distinguished by the way of partitioning the matrix and the allocation to the processors. The analysis of the behavior of the algorithms is performed in the solution of systems of linear superior triangular equations in a cluster of computers. For this, the arithmetic time, communication time, speed-up, and maximum efficiency metrics are taken into account. Experiments were performed for each algorithm with different matrix sizes on various processors. The algorithm with the best results was the one that blocks the rows of the matrix and applies a cyclical distribution in the cluster.
Downloads
References
R. Marichal, E. Dufrechou, and P. Ezzatti, “Assessing the solution of one sparse triangular linear system on multi-many core platforms,” 2019.
V. Sonzogni, P. Sanchez, and M. Storti, “Resolución de grandes sistemas de ecuaciones en un cluster de computadoras,” Mecánica Computacional, vol. 23, pp. 3211–3227, 2004.
L. Chuquiguanca, E. Malla, F. Ajila, and R. Guamán, “Arquitectura Clúster de Alto Rendimiento Utilizando Herramientas de Software Libre High Performance Cluster Architecture Using Free Software Tools,” vol. 2, no. 1, 2015.
J. L. Bolaño Herazo, “Estudio de rendimiento para la solución de ecuaciones lineales usando computación en paralelo,” 2015.
J. D. Jaramillo, A. M. V. Maciá, and F. J. C. Zabala, “Métodos directos para la solución de sistemas de ecuaciones lineales simétricos, indefinidos, dispersos y de gran dimensión,” Universidad Eafit, 2006.
C. Baeza Sanz, “Explotación de una política de partición de datos para aplicaciones paralelas,” 2015.
S. Piña, “El impacto de shocks contractivos de política monetaria en un modelo DSGE estimado con métodos bayesianos para Chile,” 2016.
H. L. Bodlaender and T. Hagerup, “Parallel algorithms with optimal speedup for bounded treewidth,” SIAM Journal on Computing, vol. 27, no. 6, pp. 1725–1746, 1998.
C. Gómez Crespo, “Diseño y evaluación de un cluster HPC: aplicaciones,” thesis, Universitat Politècnica de Catalunya, 2014.
P. E. Leibovich, F. Issouribehere, and J. C. Barbero, “Ensayo y comparación de métodos de transmisión de sincrofasores sobre redes Ethernet,” in XVIII Encontro Regional Ibero-Americano do CIGRE (ERIAC 2019)(Foz do Iguaçu, Brasil, 19 a 23 de maio de 2019), 2019.
G. H. A. Salinas and E. M. A. Salinas, “Utilización de CLAPACK para resolver sistemas de ecuaciones lineales mediante paralelismo y optimización de memoria,” UNACIENCIA, vol. 2, no. 3, pp. 7–7, 2009.
P. Ezzatti, E. S. Quintana-Ortí, and A. Remón, “Resolución de sistemas triangulares en tarjetas Gráficas (gpu),” Mecánica Computacional, vol. 29, no. 30, pp. 3053–3061, 2010.
M. Hernández, A. A. Del Barrio, and G. Botella, “Clúster de Computación Científica de Bajo Coste y Consumo,” 2018.
J. B. B. Darmawan and S. Mungkasi, “Parallel computations using a cluster of workstations to simulate elasticity problems,” in Journal of Physics: Conference Series, 2016, vol. 776, p. 012081.
I. S. Silva, L. O. Luz, R. Nepomuceno, and J. C. dos Santos, “Programaçao de processadores multi-core: Uma experiência educacional utilizando plataformas didáticas embarcadas em fpga,” International Journal in Computer Architecture Education (IJCAE), vol. 3, no. 1, pp. 9–12, 2014.
Copyright (c) 2020 Innovation and Software
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors exclusively grant the right to publish their article to the Innovation and Software Journal, which may formally edit or modify the approved text to comply with their own editorial standards and with universal grammatical standards, prior to publication; Likewise, our journal may translate the approved manuscripts into as many languages as it deems necessary and disseminates them in several countries, always giving public recognition to the author or authors of the research.
